class Solution {
public:
    string stk;
    vector<string> ans;
    vector<string> board={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    void dfs(int pos,string& digits)
    {
        if(pos==digits.size())
        {
            ans.push_back(stk);
            return;
        }
        int num=digits[pos]-'0';
        for(int i=0;i<board[num].size();i++)
        {
            stk.push_back(board[num][i]);
            dfs(pos+1,digits);
            stk.pop_back();
        }
    }
    vector<string> letterCombinations(string digits) {
        if(digits.size()==0)
            return ans;
        dfs(0,digits);
        return ans;

    }
};